package com.techyuan.algorithm.dp;

/**
 * 最长公共子序列
 * Created by Administrator on 2017/2/22.
 */
public class LCS {

    public static int[][][] lcs(char[] a, char[] b) {
        //-1：↖ -2:↑ -3:←
        int[][][] r = new int[2][a.length + 1][b.length + 1];

        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    r[0][i][j] = r[0][i - 1][j - 1] + 1;
                    r[1][i][j] = -1;
                } else if (r[0][i - 1][j] >= r[0][i][j - 1]) {
                    r[0][i][j] = r[0][i - 1][j];
                    r[1][i][j] = -2;
                } else {
                    r[0][i][j] = r[0][i][j - 1];
                    r[1][i][j] = -3;
                }
            }
        }
        return r;
    }

    public static void main(String[] args) {
        char[] aArr = new char[]{'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char[] bArr = new char[]{'B', 'D', 'C', 'A', 'B', 'A'};
        int[][][] ret = lcs(aArr, bArr);
        int i = aArr.length, j = bArr.length;
        System.out.println("最长公共子序列，长度为:" + ret[0][i][j]);
        String lcs = "";
        while (i > 0 && j > 0) {
            if (ret[1][i][j] == -1) {
                lcs = aArr[i - 1] + lcs;
                i--;
                j--;
            } else if (ret[1][i][j] == -2)
                i--;
            else
                j--;
        }
        System.out.println("最长公共子序列为:" + lcs);
    }
}
